<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from typetutorial.tnf on 19 December 2010 -->

<TITLE>Tutorial on Type Analysis - Function Types</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM>
<A HREF="http://eli-project.sourceforge.net/">
<IMG SRC="gifs/elilogo.gif" BORDER=0>
</A>&nbsp;
</TD>
<TD WIDTH="25" VALIGN=BOTTOM>
<img src="gifs/empty.gif" WIDTH=25 HEIGHT=25>
</TD>
<TD ALIGN=LEFT WIDTH="475" VALIGN=BOTTOM>
<A HREF="index.html"><IMG SRC="gifs/title.png" BORDER=0></A>
</TD>
<!-- |DELETE FOR SOURCEFORGE LOGO|
<TD>
<a href="http://sourceforge.net/projects/eli-project">
<img
  src="http://sflogo.sourceforge.net/sflogo.php?group_id=70447&amp;type=13"
  width="120" height="30"
  alt="Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads"/>
</a>
</TD>
|DELETE FOR SOURCEFORGE LOGO| -->
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_1.html#SEC1">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<A HREF="mailto:eli-project-users@lists.sourceforge.net">
<IMG SRC="gifs/button_mail.gif" BORDER=0 ALIGN="left"></A>
<A HREF="index.html"><IMG SRC="gifs/home.gif" BORDER=0 ALIGN="right"></A>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>Tutorial on Type Analysis</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_10.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_12.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<H1><A NAME="SEC15" HREF="typetutorial_toc.html#SEC15">Function Types</A></H1>
<P>
We finally extend our language towards the orthogonal use of
functions, i.e. wherever a typed entity is allowed it can
have a function type. In particular, evaluation of an expression
may yield a function, which may be called, assigned to a variable,
passed as an argument, or returned as a function result.
For that purpose it is sufficient to add another
<CODE>TypeDenoter</CODE> which denotes function types. New notations 
for expressions are not needed.
<P>
Here is an example program that defines a function type
and a higher order function:
<P>
<B>FctTypeExamp</B>[127]==
<PRE>
begin
  fun mul (int x, real y) real
  begin return x * y; end;

  fun add (int x, real y) real
  begin return x + y; end;

  type (int, real -&#62; real) fct;

  fun apply2 (real z, fct ff) real
  begin return ff (2, z); end;

  var real r;

  r = apply2 (3.1, add);
  r = apply2 (3.1, mul);
end
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
The following productions are added to the grammer:
<P>
<I>Abstract function type syntax</I>[128]==
<PRE>
RULE: TypeDenoter  ::=    FunctionType END;
RULE: FunctionType ::=    '(' ParamTypes '-&#62;' TypeDenoter ')' END;
RULE: ParamTypes   LISTOF ParamType END;
RULE: ParamType    ::=    TypeDenoter END;
</PRE>
<PRE>
This macro is invoked in definition 133.
</PRE>
<P>
The specifications for <CODE>FunctionType</CODE>s exactly correspond
to those for <CODE>FunctionHead</CODE>s in the context of function
declarations. An Operator is created, that has a signature as
given by the types of the parameters and of the result:
<P>
<I>Function type denotation</I>[129]==
<PRE>
RULE: TypeDenoter ::= FunctionType COMPUTE
  TypeDenoter.Type = FunctionType.Type;
END;

SYMBOL FunctionType INHERITS TypeDenotation, OperatorDefs END;

RULE: FunctionType ::= '(' ParamTypes '-&#62;' TypeDenoter ')' COMPUTE
  FunctionType.GotOper =
     ListOperator (
       FunctionType.Type,
       FunctionType.Type,
       ParamTypes.OpndTypeList,
       TypeDenoter.Type);

 .moreTypeProperies =
    ORDER
      (ResetTypeName (FunctionType.Type, "function..."),
       ResetTypeLine (FunctionType.Type, LINE));
END;
</PRE>
<PRE>
This macro is invoked in definition 133.
</PRE>
<P>
The introduction of function types to our language allows programs
to use values which represent functions. They have a function type
which must fit to the type required in the context.
For example, the <CODE>apply2 (3.1, add)</CODE> passes the function
<CODE>add</CODE> as an argument of the called function <CODE>apply2</CODE>.
Hence, the type of the declared function <CODE>add</CODE> must be
equivalent to the type required for the second parameter of 
<CODE>apply2</CODE> (or coercible under type rules for parameter,
as specified in the chapter on functions).
<P>
In this case we have to specify structural equivalence of function
types, in oder to let the type rules allow such uses of functions.
If we would specify name equivalence instead, then for the above 
example, the signature of the function declaration and the
type <CODE>fct</CODE> specified for the second parameter of <CODE>apply2</CODE>
are different notations of types. They would be considered
not to be name equivalent; but, they are structural equivalent.
<P>
Structural type equivalence is specified for denotations of 
function types that either occur in a type denotation or
as the signature of a declared function.
We state that two types <CODE>a</CODE> and <CODE>b</CODE> are equivalent
if both have the kind <CODE>FunctionClass</CODE>, and the component
types, which are the types of the parameters and of the result,
are elementwise equivalent:
<P>
<I>Function type equivalence</I>[130]==
<PRE>
RULE: FunctionHead ::= '(' Parameters ')' TypeDenoter COMPUTE
  FunctionHead.GotType = 
    ORDER (
      AddTypeToBlock (
         FunctionHead.Type, FunctionClass,
         VResetComponentTypes 
           (FunctionHead.Type, 
            ConsDefTableKeyList
              (TypeDenoter.Type, Parameters.OpndTypeList))),
         ResetTypeName (FunctionHead.Type, "function..."),
         ResetTypeLine (FunctionHead.Type, LINE));
END;

RULE: FunctionType ::= '(' ParamTypes '-&#62;' TypeDenoter ')' COMPUTE
  FunctionType.GotType =
    AddTypeToBlock
      (FunctionType.Type, FunctionClass,
         VResetComponentTypes 
           (FunctionType.Type, 
            ConsDefTableKeyList
             (TypeDenoter.Type, ParamTypes.OpndTypeList)))
  &#60;- .moreTypeProperies;
END;

SYMBOL ParamTypes INHERITS OpndTypeListRoot END;
SYMBOL ParamType INHERITS OpndTypeListElem END;

RULE: ParamType ::= TypeDenoter COMPUTE
  ParamType.Type = TypeDenoter.Type;
END;
</PRE>
<PRE>
This macro is invoked in definition 133.
</PRE>
<P>
<I>Function class</I>[131]==
<PRE>
FunctionClass;
</PRE>
<PRE>
This macro is invoked in definition 132.
</PRE>
<P>
We require for our language, that a function type <CODE>f</CODE> may not
directly or indirectly have a component type <CODE>f</CODE>, unless the
recursion passes through a pointer type. The check is specified
in the context of type definitions.
<P>
<B>FunctionType.pdl</B>[132]==
<PRE>
<I>Function class</I>[131]
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
<B>FunctionType.lido</B>[133]==
<PRE>
<I>Abstract function type syntax</I>[128]
<I>Function type denotation</I>[129]
<I>Function type equivalence</I>[130]
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
<B>FunctionType.con</B>[134]==
<PRE>
<I>Function type syntax</I>[142]
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_10.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_12.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>
